package leetcode;

/**
 * @author caifangyi
 * @date 2022/7/20
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 二维网格迁移
 * 
 * 给你一个 m 行 n列的二维网格grid和一个整数k。你需要将grid迁移k次。
 *
 * 每次「迁移」操作将会引发下述活动：
 *
 * 位于 grid[i][j]的元素将会移动到grid[i][j + 1]。
 * 位于grid[i][n- 1] 的元素将会移动到grid[i + 1][0]。
 * 位于 grid[m- 1][n - 1]的元素将会移动到grid[0][0]。
 * 请你返回k 次迁移操作后最终得到的 二维网格。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
 * 输出：[[9,1,2],[3,4,5],[6,7,8]]
 * 示例 2：
 *
 *
 *
 * 输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
 * 输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
 * 示例 3：
 *
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
 * 输出：[[1,2,3],[4,5,6],[7,8,9]]
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shift-2d-grid
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Day1260 {
    public static void main(String[] args) {

        int[][] grid = {{3,8,1,9},{19,7,2,5},{4,6,11,10},{12,0,21,13}};

        Solution2 solution = new Solution2();
        List<List<Integer>> lists = solution.shiftGrid(grid, 4);


        for (int i = 0; i < lists.size(); i++) {
            String collect = lists.get(i).stream().map(integer -> String.valueOf(integer)).collect(Collectors.joining(","));
            System.out.println(collect);
        }
    }

    static class Solution2 {

        /**
         * 把二维数组看作一维数组
         * @param grid
         * @param k
         * @return
         */
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {
            int m = grid.length;
            int n = grid[0].length;

            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                List<Integer> list1 = new ArrayList<>();
                for (int i1 = 0; i1 < n; i1++) {
                    list1.add(0);
                }
                list.add(list1);
            }


            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int index = ( i*n + j + k ) % (m * n);
                    list.get(index/n).set(index%n, grid[i][j]);
                }
            }
            return list;
        }


    }

    static class Solution {
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {

            int[][] gridNew = new int[grid.length][grid[0].length];
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    int i1 = (i + (j + k) / grid[i].length ) % grid.length;
                    int i2 = (j + k) % grid[i].length;
                    gridNew[i1][i2] = grid[i][j];
                }
            }

            List<List<Integer>> mList = new ArrayList();
            for (int i = 0; i < gridNew.length; i++) {
                List<Integer> nlist = new ArrayList<>();
                for (int j = 0; j < gridNew[i].length; j++) {
                    nlist.add(gridNew[i][j]);
                }
                mList.add(nlist);
            }
            return mList;
        }
    }
}
